package ThirdWeek;

import java.util.Arrays;
import java.util.HashMap;

public class Monday {
    //力扣：28. 找出字符串中第一个匹配项的下标
    public int strStr(String haystack, String needle) {
        int n = haystack.length(),m = needle.length();
        char[] hh = haystack.toCharArray();
        char[] nn = needle.toCharArray();
        for (int i = 0; i <= n - m; i++) {
            int cur = i,dest = 0;
            while(dest < m && hh[cur] == nn[dest]) {
                cur++;
                dest++;
            }
            if (dest == m) {
                //说明正好比较结束，返回
                return i;
            }
        }
        return -1;
    }

    //力扣：14. 最长公共前缀
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }else {
            //分治
            return longestCommon(strs,0,strs.length - 1);
        }
    }
    private static String longestCommon(String[] strs,int start,int end) {
        if (start == end) {
            //递归的结束条件
            return strs[start];
        }else {
            int mid = (end + start) / 2;
            //递归找到最左面的字符串，和其相邻的字符串进入到Common中找到最小的长度相等的字符串给到lcpLeft
            String lcpLeft = longestCommon(strs,start,mid);
            //和上面的递归相似，最后给到lcpRight
            String lcpRight = longestCommon(strs,mid + 1,end);
            //最后一次比较返回给longestCommon
            return Common(lcpLeft,lcpRight);
        }
    }

    private static String Common(String lcpLeft, String lcpRight) {
        //比较两个字符串谁最小，寻找最小的字符串可以减少比较次数
        int MinLength = Math.min(lcpLeft.length(),lcpRight.length());
        for (int i = 0; i < MinLength; i++) {
            //当不相等的时候，就会返回最长的相等长度，
            if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
                return lcpLeft.substring(0,i);
            }
        }
        return lcpLeft.substring(0,MinLength);
    }


    //力扣：13. 罗马数字转整数
    HashMap<Character,Integer> map = new HashMap<>() { {
      put('I',1);
      put('V',5);
      put('X',10);
      put('L',50);
      put('C',100);
      put('D',500);
      put('M',1000);
    } };
    public int romanToInt(String s) {
        int sum = 0,n = s.length();
        for (int i = 0; i < n; i++) {
            int value = map.get(s.charAt(i));
            //最后的一个数值一定是往上加的，不会是减
            //所以在 0 —— n-1 范围之间进行查找
            if (i < n - 1 && value < map.get(s.charAt(i + 1))) {
                //这个时候是前一个数字是小于后一个数字的，比如 “IV” 就是 -1 + 5 = 4
                sum -= value;
            }else {
                sum += value;
            }
        }

        return sum;
    }

    public static void main(String[] args) {
        String[] strs = {"flower","flower","flower","flower"};
        System.out.println(longestCommonPrefix(strs));
    }
}
